package com.fzk.core.lru;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * 双向链表
 *
 * @author fzk
 * @datetime 2023-05-11 22:01:31
 */
public class NodeList<K, V> {
    private final Node<K, V> head;
    private final Node<K, V> tail;
    private final HashMap<K, Node<K, V>> map;

    public NodeList() {
        head = new Node<>(null, null, null, null);
        tail = new Node<>(null, null, null, null);
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }

    public boolean containsKey(K key) {
        return map.containsKey(key);
    }

    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            return node.val;
        }
        return null;
    }

    /**
     * 若存在，则更新val且移动到队头，否则新建结点移到队头
     *
     * @return 可能存在的旧值，不存在为null
     */
    public V putHead(K key, V val) {
        V old = null;
        if (map.containsKey(key)) {
            // 更新并移到队头
            old = replace(key, val);
            moveToHead(key);
        } else {
            Node<K, V> node = new Node<>(head, head.next, key, val);
            // 放入map
            map.put(key, node);
            // 插入队首
            head.next.pre = node;
            head.next = node;
        }
        return old;
    }

    /**
     * 若存在，则更新val且移动到队尾，否则新建结点移到队尾
     *
     * @return 可能存在的旧值，不存在为null
     */
    public V putTail(K key, V val) {
        V old = null;
        if (map.containsKey(key)) {
            // 更新并移到队尾
            old = replace(key, val);
            moveToTail(key);
        } else {
            Node<K, V> node = new Node<>(tail.pre, tail, key, val);
            // 放入map
            map.put(key, node);
            // 插入队尾
            tail.pre.next = node;
            tail.pre = node;
        }
        return old;
    }

    public V replace(K key, V val) {
        V old = null;
        Node<K, V> node = map.get(key);
        if (node != null) {
            old = node.val;
            node.val = val;
        }
        return old;
    }

    public void moveToHead(K key) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            // 不在队头才移动，否则会引用循环
            if (head.next != node) {
                // 先将node从原来位置移除，再重新加入
                removeNode(node);

                node.pre = head;
                node.next = head.next;
                head.next.pre = node;
                head.next = node;
            }
        }
    }

    public void moveToTail(K key) {
        Node<K, V> node = map.get(key);
        if (node != null) {
            // 不在队尾才移动，否则会引用循环
            if (tail.pre != node) {
                // 先将node从原本位置移除，再重新加入
                removeNode(node);
                node.pre = tail.pre;
                node.next = tail;
                tail.pre.next = node;
                tail.pre = node;
            }
        }
    }

    public Node<K, V> removeHead() {
        if (size() == 0) {
            return null;
        }
        Node<K, V> node = head.next;
        // 从map移除
        map.remove(node.key);
        // 从链表移除
        removeNode(node);
        return node;
    }

    public Node<K, V> removeLast() {
        if (map.size() == 0) {
            return null;
        }
        Node<K, V> node = tail.pre;
        // 从map移除
        map.remove(node.key);
        // 从链表移除
        removeNode(node);
        return node;
    }

    public V remove(K key) {
        // 从map移除
        Node<K, V> node = map.remove(key);
        if (node != null) {
            // 从链表移除
            removeNode(node);
            return node.val;
        }
        return null;
    }

    // 从链表中删除该节点
    private void removeNode(Node<K, V> node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = null;
        node.next = null;
    }

    public int size() {
        return map.size();
    }

    // 瞬间快照
    public ArrayList<Node<K, V>> toArray() {
        ArrayList<Node<K, V>> result = new ArrayList<>(map.size());
        if (map.size() == 0) {
            return new ArrayList<>();
        }
        Node<K, V> cur = head;
        while (cur != tail) {
            result.add(new Node<>(null, null, cur.key, cur.val));
            cur = cur.next;
        }
        return result;
    }

    public void clear() {
        map.clear();
        head.next = tail;
        tail.pre = head;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        Node<K, V> node = head.next;
        while (node != tail) {
            sb.append(node.key).append(": ").append(node.val).append(", ");
            node = node.next;
        }
        if (sb.length() > 2) {
            sb.delete(sb.length() - 2, sb.length());
        }
        sb.append('}');
        return sb.toString();
    }

    public void checkList() {
        HashSet<Node<K, V>> set = new HashSet<>();
        ArrayList<Node<K, V>> list = new ArrayList<>();
        Node<K, V> node = head.next;
        // 从头部到尾巴检查
        while (node != tail) {
            list.add(node);
            boolean add = set.add(node);
            if (!add) {
                throw new RuntimeException("非法");
            }
            node = node.next;
        }
        if (list.size() != map.size()) {
            throw new RuntimeException("非法");
        }
        // 从尾部到头部检查
        node = tail.pre;
        int index = list.size() - 1;
        while (node != head) {
            if (!set.contains(node)) {
                throw new RuntimeException("非法");
            }
            if (node != list.get(index)) {
                throw new RuntimeException("非法");
            }
            node = node.pre;
            index--;
        }
    }

    public static class Node<K, V> {
        public Node<K, V> pre;
        public Node<K, V> next;
        public K key;
        public V val;

        public Node(Node<K, V> pre, Node<K, V> next, K key, V val) {
            this.pre = pre;
            this.next = next;
            this.key = key;
            this.val = val;
        }
    }
}
